Theory of Computation
Q141.
Let < M > denote an encoding of an automaton M. Suppose that \Sigma =\{0,1\}. Which of the following languages is/are NOT recursive?Q142.
If L and P are two recursively enumerable languages then they are not closed underQ143.
Given the following statementsS1 : Every context-sensitive language L is recursiveS2 : There exists a recursive language that is not context-sensitiveWhich statements are true?Q146.
Nobody knows yet if P = NP. Consider the language L defined as follows : L=\left\{\begin{matrix} (0+1)^{*}\; \; \; if P=NP\\ \Phi \; \; otherwise \end{matrix}\right. Which of the following statements is true ?Q147.
Let L be a language and \bar{L} be its complement. Which of the following is NOT a viable possibility?Q149.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that \bar{Y} reduces to W, and Z reduces to \bar{X} (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?Q150.
Let L1 be regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?